package leetcode.weekly.week328;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

//Solution4Test
public class Solution4 {

	List<Set<Integer>> nexts;
	int[] price;
	long[] f, s;
	int[] f2, s2;
	long ans;

	public long maxOutput(int n, int[][] edges, int[] price) {
		f = new long[n];// 节点作为根时最长链价值
		s = new long[n];// 节点作为根时次长链价值
		f2 = new int[n];// f2[i] = next，i同next产生的最长链
		s2 = new int[n];// s2[i] = next，i同next产生的次长链
		this.price = price;
		nexts = new ArrayList<>();// 构图
		for (int i = 0; i < n; i++) {
			nexts.add(new HashSet<>());
		}
		for (int i = 0; i < edges.length; i++) {
			int[] e = edges[i];
			int a = e[0], b = e[1];
			nexts.get(a).add(b);
			nexts.get(b).add(a);
		}
		// 构建基础的各个节点的，最长，次长，最长次长的next即f,s,f2,s2信息
		f(0, -1);
		ans = 0;
		// 从0开始收集答案并且向下级转移
		s(0, -1);
		return ans;
	}

	private void s(int i, int p) {
		ans = Math.max(ans, f[i] - price[i]);
		Set<Integer> next = nexts.get(i);
		for (int n : next) {
			if (n == p) {
				continue;
			}
			long fv = f[n], sv = s[n];
			int fv2 = f2[n], sv2 = s2[n];
			if (n == f2[i]) {// 要去曾经最长，只能用用曾经次长 + 下级节点比
				if (s[i] + price[n] > f[n]) {
					s2[n] = f2[n];
					s[n] = f[n];
					f[n] = s[i] + price[n];
					f2[n] = i;
				} else if (s[i] + price[n] > s[n]) {
					s[n] = s[i] + price[n];
					s2[n] = i;
				}
			} else {// 要去的不是最长，用曾经最长 + 下级节点比
				if (f[i] + price[n] > f[n]) {
					s2[n] = f2[n];
					s[n] = f[n];
					f[n] = f[i] + price[n];
					f2[n] = i;
				} else if (f[i] + price[n] > s[n]) {
					s[n] = f[i] + price[n];
					s2[n] = i;
				}
			}
			s(n, i);// 去下级找答案
			// 回溯
			f[n] = fv;
			s[n] = sv;
			f2[n] = fv2;
			s2[n] = sv2;
		}
	}

	private long f(int i, int p) {
		Set<Integer> next = nexts.get(i);
		f[i] = price[i];
		s[i] = price[i];
		for (int n : next) {
			if (n == p) {
				continue;
			}
			long cur = f(n, i) + price[i];
			if (cur > f[i]) {
				s[i] = f[i];
				f[i] = cur;
				s2[i] = f2[i];
				f2[i] = n;
			} else if (cur > s[i]) {
				s[i] = cur;
				s2[i] = n;
			}
		}
		return f[i];
	}

}
